// 左右乘积列表

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, 0), right(n, 0);
        left[0] = 1;  // 左侧没有元素
        for(int i = 1; i < n; ++i)
        {
            left[i] = nums[i-1] * left[i-1];
        }
        right[n-1] = 1; // 右侧没有元素
        for(int i = n-2; i >= 0; --i)
        {
            right[i] = nums[i+1]*right[i+1];
        }
        vector<int> answer(n);
        for(int i = 0; i < n; ++i)
        {
            answer[i] = left[i] * right[i]; 
        }
        return answer;
    }
};

// 优化空间复杂度 O(1)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> answer(n);
        answer[0] = 1; // 左侧没有元素
        for(int i = 1; i < n; ++i)
        {
            answer[i] = nums[i-1] * answer[i-1];
        }
        int right = 1;
        for(int i = n - 1; i >= 0; --i)
        {
            answer[i] = right * answer[i];
            right *= nums[i];
        }
        return answer;
    }
};